package com.trainoo.leetcode;

/**
 * <p> 验证回文串 </p>
 * https://leetcode-cn.com/problems/valid-palindrome/
 *
 * 示例 1:
 * 输入: "A man, a plan, a canal: Panama"
 * 输出: true
 *
 * 示例 2:
 * 输入: "race a car"
 * 输出: false
 *
 * @author tao.zhou
 * @version 1.0
 * @date 2020/6/19 17:25
 */
public class Q0125 {

    public static void main(String[] args) {
        String test1 = "A man, a plan, a canal: Panama";
        String test2 = "Aa man, a plan, a canal: Panamaa";
        System.out.println(new Solution().isPalindrome(test2));
    }

    static class Solution {

        public boolean isPalindrome(String s) {
            StringBuilder sb = new StringBuilder();
            // 去除空格字符并转小写
            for (int i=0; i < s.length(); i ++){
                if (Character.isLetterOrDigit(s.charAt(i))){
                    sb.append(Character.toLowerCase(s.charAt(i)));
                }
            }
            // 判断翻转前后是否一样
            return sb.toString().equals(sb.reverse().toString());
        }

        /**
         * 双指针
         */
        public boolean isPalindrome2(String s) {
            int left = 0;
            int right = s.length() - 1;

            while (left < right){
                while (left < right && !Character.isLetterOrDigit(s.charAt(left))) {
                    ++ left;
                }
                while (left < right && !Character.isLetterOrDigit(s.charAt(right))) {
                    -- right;
                }
                if (left < right) {
                    if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
                        return false;
                    }
                    ++left;
                    --right;
                }
            }
            return true;
        }
    }
}
